import java.util.*;
import java.io.*;

public class Merger {
  static Queue<Node> queue = new LinkedList<Node>();
  public static void mergeWith(SuffixTree main, SuffixTree tmp, Braf mainBraf, Braf tmpBraf) {
    Node mainNode = main.getRootNode();
    Node tmpNode = tmp.getRootNode();
    mergeWith(mainNode, tmpNode, mainBraf, tmpBraf, main);
  }

  private static void newNames(Node startNode, SuffixTree main) {
    startNode.setName(main.getNewNodeNumber());
    queue.add(startNode);
    while (!queue.isEmpty()) {
      Node node = queue.remove();
      for (Edge edge : node.getEdges()) {

        node.setName(main.getNewNodeNumber());

        if (edge.getEndNode() != null)
          queue.add(edge.getEndNode());
      }
    }
  }

  private static void mergeWith (Node mainNode, Node tmpNode, Braf mainBraf, Braf tmpBraf, SuffixTree main) {
    for (char tmpChar: tmpNode.getKeys()) {
      if (!mainNode.containsKey(tmpChar)) {
        Edge foundEdge = tmpNode.findEdge(tmpChar);//take the found edge.
        foundEdge.setStartNode(mainNode);//change the startnode to point to main suffixtree
        newNames(foundEdge.getEndNode(), main);//rename all the child nodes of found edge
        foundEdge.insert();//insert found edge on the startnode
//        Edge newEdge = new Edge(foundEdge.getBeginIndex(), foundEdge.getCharIndex(), foundEdge.getEndIndex(), mainNode, foundEdge.getEndNode());
//        newEdge.insert();
      } else { //omg it exists... difficile
        Edge mainEdge = mainNode.findEdge(tmpChar);
        Edge tmpEdge = tmpNode.findEdge(tmpChar);
        try {
          Node fakeNode = new Node(-1);
          boolean breaker = false;
          int mainInt = -1;
          int tmpInt = -1;
          int i;
          mainBraf.seek((long) mainEdge.getBeginIndex());
          tmpBraf.seek((long) tmpEdge.getBeginIndex());

          for (i = 0; i <= Math.min(mainEdge.getSpan(), tmpEdge.getSpan()); i++) {//loop through every character in the 2 edges
            mainInt = mainBraf.read();
            tmpInt = tmpBraf.read();
            if (mainInt != tmpInt) {//found the point of difference
              Node newEndNode = mainEdge.splitEdge(i-1, (char) mainInt, main.getNewNodeNumber());//i-1 is the last character of the first part of the split edge.

//              Edge newEdge = new Edge(tmpEdge.getBeginIndex() + i, (char) tmpInt, tmpEdge.getEndIndex(), newEndNode, tmpEdge.getEndNode());//copying the different part of the tmpEdge


              tmpEdge.incBeginIndex(i);
              tmpEdge.setCharIndex((char) tmpInt);
              tmpEdge.setStartNode(newEndNode);



//              newNames(newEdge.getEndNode(), main);//renaming child nodes
//              newEdge.insert();//inserting  it in the newEndNode of main edge
              newNames(tmpEdge.getEndNode(), main);
              tmpEdge.insert();
              breaker=true;
              break;
            }
          }
          if (!breaker) {
            //didn't find the break point yet
            if (mainEdge.getSpan() < tmpEdge.getSpan()) {//reached the end of mainEdge without finding a break point
              //System.out.println("main<tmp");
              tmpInt = tmpBraf.read();
              if (mainEdge.getEndNode().findEdge((char) tmpInt) == null) {//if the next character of tmpEdge doesn't exist in main, we'll just hung a new Edge
                
         //       Node newEndNode = tmpEdge.splitEdge(i-1, (char) tmpInt, main.getNewNodeNumber());

//                Edge newTmpEdge = new Edge(tmpEdge.getBeginIndex(), tmpEdge.getCharIndex(), tmpEdge.getEndIndex(), new Node(main.getNewNodeNumber()), tmpEdge.getEndNode()); //copying the mainEdge
 //               Node newEndNode = newTmpEdge.splitEdge(i-1, (char) tmpInt, main.getNewNodeNumber());

                tmpEdge.incBeginIndex(i);
                tmpEdge.setCharIndex((char) tmpInt);
                tmpEdge.setStartNode(mainEdge.getEndNode());
                newNames(tmpEdge.getEndNode(), main);
                tmpEdge.insert();

//                Edge newEdge = newEndNode.findEdge((char) tmpInt);

//                newEdge.setStartNode(mainEdge.getEndNode());
//                newNames(newEdge.getEndNode(), main);
//                newEdge.insert();


              } else {

//                Edge newTmpEdge = new Edge(tmpEdge.getBeginIndex(), tmpEdge.getCharIndex(), tmpEdge.getEndIndex(), new Node(main.getNewNodeNumber()), tmpEdge.getEndNode()); //copying the mainEdge

//                Node newEndNode = newTmpEdge.splitEdge(i-1, (char) tmpInt, main.getNewNodeNumber());//i split the tmpEdge
                tmpEdge.incBeginIndex(i);
                tmpEdge.setCharIndex((char) tmpInt);
                tmpEdge.setStartNode(fakeNode); //need a fake tmp Node here
                tmpEdge.insert();
                mergeWith(mainEdge.getEndNode(), fakeNode, mainBraf, tmpBraf, main);

                
//                Node newEndNode = tmpEdge.splitEdge(i-1, (char) tmpInt, main.getNewNodeNumber());//i split the tmpEdge
//                mergeWith(mainEdge.getEndNode(), newEndNode, mainBraf, tmpBraf, main);
              }
            } else if (mainEdge.getSpan() > tmpEdge.getSpan()) {//reached the end of mainEdge without finding a break point
              mainInt = mainBraf.read();
              Node newEndNode = mainEdge.splitEdge(i-1, (char) mainInt, main.getNewNodeNumber());
              mergeWith(newEndNode, tmpEdge.getEndNode(), mainBraf, tmpBraf, main);
            } else {
              mergeWith(mainEdge.getEndNode(), tmpEdge.getEndNode(), mainBraf, tmpBraf, main);
            }
          }
        } catch (Exception e) {
          System.out.println("ERROR in merging: " + e.getMessage());
          e.printStackTrace();
        }
      } 
    }
  }
}
